
//853.车队
class Solution {
public:
    int carFleet(int target, vector<int>& position, vector<int>& speed) {
        int n=position.size();

        //要先将车队的位置进行从左到右的排列
        vector<pair<int,int>> tmp(n);   
        for(int i=0;i<n;i++) tmp[i]={position[i],speed[i]};
        sort(tmp.begin(),tmp.end());    

        //存储每个车达到终点需要花费的时间
        vector<double> nums(n);  
        for(int i=0;i<n;i++)
        nums[i]=(target-tmp[i].first)/(double)tmp[i].second;

        //进行单调栈
        stack<double> st;
        for(int i=0;i<n;i++)
        {
            while(!st.empty()&&st.top()<=nums[i]) st.pop();  //如果靠近终点的车需要的时间更长,后面的车就能追上形成车队
            st.push(nums[i]);
        }
        return st.size();
    }
};